数据库扩展能力

提高扩展能力

1. scale up
   • 高性能关系数据库产品
   • 昂贵/扩展能力有限/使用简单
2. scale out
   • 更多的计算机，增加节点
   • 性价比高/扩展能力强/实现困难

若系统能做到scale out，是否自然能做到scale up？（不能）

Scale out

1. 应用层扩展（分库/分表的扩展模式）
   • 与应用相关，不是数据库内部的事情
   • 优点：不需要修改数据库内核
   • 问题
     • 负载不均
     • 业务难以拆分
   • 重点：查询分解
2. 并行/分布式数据库
   • 只有一个数据库，对用户透明
   • 如何评价扩展性？
     • 加一倍的机器，效率是否能提高一倍
   • 硬件资源的瓶颈：机器之间的通信
     • 降低带宽的使用量，才能有更好的扩展性
   • 架构设计
     • shared memory：可以访问其他计算机的内存/磁盘
       • 任何内存/磁盘的读写都是通信
     • shared disk：共享磁盘
       • 内存在本地读，磁盘通信
     • shared nothing（最强的）：每个进程只能访问本机的资源，可以与其他进程进行通信
       • 在本地操作，使传输数据尽可能小（处理的中间结果）
       • 但实现复杂，划分数据困难

如何划分数据

1. 根据业务划分
2. Round-robin（轮询调度算法）：每次的请求都按照节点顺序依次分配
   • 负载均衡
   • 不适合点/范围查询
   • 对顺序查询友好
3. Hash partitioning
   • 对点查询/join友好
   • 不适合范围查询/非key值查询
   • 负载较为均衡
4. Range patitioning：根据key范围进行划分
   • 对在key值上的范围查询友好
   • 需要存储partition vector（不均衡的）

如何执行查询

• 关系代数的并行化
  • 选择/投影/join都可以并行化
• join的并行化
  • 半连接（semi-join）
    • 不需要传输完整的数据，减少消息传递的开销
    • 先在key上做投影，只发送key给另一个table
  • broadcasting join
    • 对于小表而言，可以将其发送到另一个表的每一个节点
    • 也可以先在局部做了排序后再发送（parallel external sort-merge）
  • partitioned join
    • 使用同样的hash函数，将两个table同样的key映射到一个机器做local join

分布式数据库事务

对比

分库/分表的扩展模式

• 缺点
  • 数据难以拆分
  • 事务处理困难
• 将事务拆分，能保证ACID吗？
  • 一般很难保证
• 由中间键（middleware）保证，需要DB与中间键配合，提供特殊的接口

并行/分布式数据库

• 优点
  • 不需要拆分或子查询
  • SQL可以并行化
  • 事务不需要中间层处理
• 缺点
  • 实现复杂
  • 节点之间通信很多
  • 对应用透明，不会根据不同的查询来优化SQL，扩展性不一定好

分布式并发控制

如何实现分布式的可线性化：

1. 需要保证每个节点的可线性化（local schedule）
2. 需要保证全局的可线性化（global schedule）
   • 保证每个节点的事务处理顺序都一样

实现方式

1. Locking
   • Centralized 2PL
     • 在单点维护所有的锁信息和锁管理器
     • 会造成单点压力过大，扩展性差
     • 但容易检测到死锁
   • Distributed 2PL
     • 每个节点加锁，同时直接在该节点操作
     • 扩展性更强，但不容易检测到死锁（需要结合多个节点信息）

Atomicity and Durability

• Two - Phase commit（两节点提交）
  • 主节点问所有的从节点是否准备好了commit，然后进行投票
  • 每个节点有自己的日志，可以用来恢复
  • 当主节点挂了，某些已经commit的从节点也挂了，这时候会blocking（不知道是否该提交），进行不下去了
• 3PC commit
  • 主要用一个precommit来解决blocking的问题
  • 在precommit之前挂掉，都可以回滚
  • 其实就是让从节点知道了整个集群的信息

扩展性问题

通信的开销分为两部分

1. 延迟
2. 为了维护数据的一致性，弥补系统的不稳定，需要经常通信

分库/分表的扩展模式：扩展性更好（NoSQL使用）

并行/分布式数据库：没有考虑到业务逻辑，可能造成通信开销大

扩展能力的关键在于数据和负载的划分：依赖于数据的局部性

NoSQL为什么扩展性比SQL强？

• 没有Join/没有事务
• 基本上没有跨节点操作
• 强迫用户层面去解决事务的问题

NoSQL的工具特点使得应用始终都在考虑扩展性问题

分布式数据库的折中点

CAP理论：任何一个分布式数据库只能在C（Consistency）/A（Availability）/P（Partitioning Tolerance）中兼顾两个。

对于分布式数据库来说，一定会面临P的问题，因此实际上是在C/A中进行选择

传统数据库

根据日志复制方式不同，可分为：

• eager：复制后再返回，属于CP
• lazy：返回后再复制，属于AP

MongoDB

通过调节read concern和write concern实现

readConcern: { level: <level> }

• local
  • 直接返回数据，不保证该数据已经被写入多数节点 (AP)
• majority
  • 返回已经被多数节点写入的数据(CP)

{ w: <value>, j: <boolean>, wtimeout: <number> }

• w
  • 0：不保证数据成功写入
  • 1：保证单点已经收到写入请求
  • majority：保证大多数节点已经收到写入请求
• j
  • true：根据w设置的节点数，保证日志已经写入磁盘

NewSQL

• 支持传统SQL的功能接口
• 支持更好的扩展性(Scale-out)（最主要）
• 支持分布式环境下的高可用
• 在低端高并行硬件(commodity hardware) 上部署

nA &sA

由于C/A我们都尽可能的想要，因此：

Node Availability (nA)

• 通信故障发生时，任一节点都可用

Service Availability (sA)

• 通信故障发生时，部分节点不可用。但是，总有一部分节点可用。系统可以将用户自动切换到可用的节点。
• 服务不中断。

CnAP vs CsAP

CnAP：只能在CP和nAP中二选一。

CsAP：在某种条件下，可以兼顾。

• Raft /Paxos
• 若网络故障，但大部分节点没有故障，可以将故障的服务转移到majority上持续提供服务
• 数据的一致性可以保证（服务的高可用）
• Spanner是利用CsAP的NewSQL

Spanner

事务

对于分布式事务处理，一般处理方法有：

• 并发控制： 2PL

• 原子性&容错：2PC

  但加锁性能太差，因此在spanner中使用 multiversion & Timestamp ordering

Timestamp-Based Protocols

每一个事务进入系统时给一个时间戳，在每个数据上维护两个时间戳，分别是：

W-timestamp（Q）：执行写事务的最大时间戳

R-timestamp（Q）：执行读事务的最大时间戳

当执行读操作时，

• 若该事务时间戳小于W-timestamp，则回滚（已经有新事务写入）；
• 否则，读取该数据，并修改R-timestamp

当执行写操作时，

• 若该事务的时间戳小于R-timestamp，则回滚（已经有新事务读取了旧数据）；
• 若该事务的时间戳小于W-timestamp，则回滚（已经有新事务写入）；
• 否则，执行写事务，并将W-timestamp设置为当前时间戳

这种方法不会造成死锁，但会出现大量回滚（cascading roolback）

解决方法

1. 写操作全部在事务的最后进行
2. 所有的写操作都是原子的，在写操作进行时不会有事务执行
3. 在读数据时等待数据commit

使用multiversion解决大量回滚的问题

multiversion schemes

每次写操作只是增加数据的一个新副本，且用时间戳进行标识

当进行操作时，总是找小于它的最大的W-timestamp的数据

• 当执行读操作时：
  • 立即返回，且更新其R-timestamps
• 当执行写操作时：
  • 若该时间戳小于R-timestamp，则回滚（本来后面的事务应该读这个事务的数据，但已经读了比它更老的数据）
  • 若该时间戳等于W-timestamp，则重写内容
  • 否则，增加一个数据的副本

区分两种事务：

1. 只读事务
   • 不加锁，可以直接读
2. 读写事务
   • 读全部加读锁（读最新的），写在commit时加写锁（代价于SQL中相同）